# 互质数的个数
import math

MOD = 998244353


def count_prime_pairs(a, b):
    """我的方法, 超时/总数=7/10"""
    s = pow(a, b)
    flag = False  # a的b次方是否是偶数
    res = 0
    if s % 2 == 0:
        flag = True
    for i in range(1, s):
        if flag and i % 2 == 0:
            continue
        else:
            if math.gcd(i, s) == 1:
                res += 1
    return res % 998244353


def count_prime_pairs_opt(a, b):
    """欧拉函数: 请问在给定正整数n, 在小于等于n中, 有多少个与n互质?
    定义: 在[1, n]中, 与n互质的数的个数成为欧拉函数, 记为phi(n)
    例如: phi(1) = 1 phi(2) = 1, phi(3) = 2, phi(4) = 2, phi(5) = 4

    欧拉函数的性质:
    1. 若p为质数, 则phi(p) = p - 1.
        因为质数在[1,p]范围内, 除了与自身不互质以外, 与任何数都互质
    2. 若p为质数, 这phi(p^k) = (p - 1) * p^(k - 1).
        数列为 [1...p...2p...3p......p^k], 我们可以将 [1,p^k] 分为 p^(k - 1) 个等长的序列, 每个序列中的互质的个数为 p - 1.
    3. 欧拉函数为积性函数: 若gcd(m, n) = 1, phi(mn) = phi(m)phi(n)

    由上易得: phi(p) = prod[p_i^(k_i - 1) * (p_i - 1)], 其中prod为求积运算.
    例如: phi(1323) = phi(3^3 * 7^2) = [3^(3 - 1) * (3 - 1)] * [7^(2 - 1) * (7 - 1)] = 9 * 2 * 7 * 6 = 759
    其中指数部分的底数(即 3^3 和 7^2 中的 3 和 7)必须为质数
    另例: phi(8) = phi(2^3) = 2^(3 - 1) * (2 - 1) = 4
    """
    # 对a分解质因数
    fact_dict = {}
    temp = a
    fact = 2
    fact_cnt = 0
    while fact <= temp:
        if temp % fact == 0:
            fact_cnt += 1
            temp = temp // fact
        else:
            if fact_cnt > 0:  # 只记录质数大于0的质因数
                fact_dict[fact] = fact_cnt
            fact += 1
            fact_cnt = 0
    fact_dict[fact] = fact_cnt  # 添加最后一个质因数

    # 计算连乘
    res = 1
    for prime, power in fact_dict.items():
        res *= (prime - 1) * pow(prime, b * power - 1, MOD)
        res %= MOD

    return res


if __name__ == '__main__':
    # a, b = map(int, input().split())
    # print(count_prime_pairs(a, b))
    print(count_prime_pairs(2, 5))  # 16
    print(count_prime_pairs(12, 7))  # 11943936
